public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestPalindrome("cbbd"));
    }
}

//二刷
class Solution {
    public String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
            dp[i][i + 1] = true;
        }
        int maxLen = 1;
        int maxLenBegin = 0;
        for (int len = 2; len <= s.length(); len++) {
            for (int begin = 0; begin + len - 1 < s.length(); begin++) {
                int end = begin + len;
                dp[begin][end] = dp[begin + 1][end - 1] && s.charAt(begin) == s.charAt(end - 1);
                if (dp[begin][end] && maxLen < len) {
                    maxLen = len;
                    maxLenBegin = begin;
                }
            }
        }
        return s.substring(maxLenBegin, maxLenBegin + maxLen);
    }
}

//class Solution {
//    public String longestPalindrome(String s) {
//
//        String longest = s.substring(0, 1);
//
//        for (int i = 1; i < s.length(); i++){
//            int j = 1, k = 1;
//            int lOdd = 1;
//
//            while (i - j >= 0 && i + k < s.length()){
//                if (s.charAt(i - j) == s.charAt(i + k)){
//                    lOdd += 2;
//                    j++;
//                    k++;
//                }
//                else{
//                    break;
//                }
//            }
//            if (lOdd > longest.length()){
//                longest = s.substring(i - j + 1, i + k);
//            }
//
//            j = 1; k = 0;
//            int lEven = 0;
//            while (i - j >= 0 && i + k < s.length()){
//                if (s.charAt(i - j) == s.charAt(i + k)){
//                    lEven += 2;
//                    j++;
//                    k++;
//                }
//                else{
//                    break;
//                }
//            }
//            if (lEven > longest.length()){
//                longest = s.substring(i - j + 1, i + k);
//            }
//        }
//        return longest;
//    }
//}